#!/bin/python
# check the JSP solution

import numpy as np
import sys

verbose = False

def check(in_file_name, out_file_name):
    with open(in_file_name) as f:

        desc = None
        njobs = -1
        nmachines = -1
        jobs = []
        for line in f:
            # read description first
            if desc is None:
                desc = line
            elif njobs < 0:
                njobs, nmachines = [int(e) for e in line.split()]
            else:
                a_job = []
                a_dur = []
                pair = []
                for e in line.split():
                    pair.append(int(e))
                    if len(pair) == 2:
                        a_job.append(pair)
                        pair = []
                jobs.append(a_job)


    machines=[]
    with open(out_file_name) as f:
        makespan = twft = -1
        for line in f:
            if len(line.strip()) == 0: continue  # for kushagra
            if makespan < 0:
                makespan, twft = [int(e) for e in line.split()]
            else:
                lst = [int(e) for e in line.split()]
                machines.append(zip(lst[::2], lst[1::2]))


    if verbose:
        for m in machines:
            print m
        for j in jobs:
            print j

    def get_duration(j, m):
        for mi, dur in jobs[j]:
            if mi == m:
                return dur

    def find_job(mach, j):
        for ji, start in mach:
            if ji == j: return start
        return -1


    ######################################################
    # check feasibility of solution
    ######################################################
    # check job order
    for ji in range(njobs):
        jend = 0
        for mi, dur in jobs[ji]:
            jstart = find_job(machines[mi], ji)

            if jstart < jend:
                print "Job ordering error!!!"
                print "\tjob(",ji, ",", mi, ") started too early!"
                print "\tstart:", jstart, "  dur:", dur, "  end:", jend
                print jobs[ji]
                sys.exit(-1)
            else:
                if verbose:
                    print "[",ji,"] ", jstart, ">=", jend
            jend = jstart + dur

    # check job assigment on each machine
    for mi in range(nmachines):
        # each achine
        end = 0
        for j, start in machines[mi]:
            dur = get_duration(j, mi)

            if start < end:
                print "Machine scheduling error!!"
                print "\tjob(",ji, ",", mi, ") started too early!"
                print "\tstart:", start, "  dur:", dur, "  end:", end
                print machines[mi]
                sys.exit(-1)
            else:
                if verbose:
                    print "[",j,"] ", start, ">=", end

            end = start + dur

    #######################################################
    # check valid cost computation
    ######################################################
    c_times = []
    for mi in range(nmachines):
        ji, start = machines[mi][-1]
        c_times.append(start + get_duration(ji, mi))

    assert(len(c_times) == nmachines)

    # check makespan cost
    mkspn_chk = np.max(c_times)

    if makespan != mkspn_chk:
        print "Wrong makespan computation (", makespan, "!=", mkspn_chk, ")"
        sys.exit(-1)

    # check twft
    twft_chk = np.sum(c_times)
    if twft != twft_chk:
        print "Wrong TWFT computation (", twft, "!=", twft_chk, ")"
        sys.exit(-1)


    print "OK: the output is feasible and valid!"
    sys.exit(0)

if __name__ == '__main__':
    if len(sys.argv) != 3:
        print "Usage:", sys.argv[0], "input output"
        sys.exit(1)
    check(sys.argv[1], sys.argv[2])